package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//逆向逐层输出树的元素
public class LevelOrderTraversalInReverse {
    @Test
    public void test(){
        int[] A={1,2,4,5,3,6,7};
        int[] B={4,2,5,1,6,3,7};
        BuildBinaryTree buildBinaryTree=new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B,A,0,6);
        levelOrderTraversalInReverse(root);//4 5 6 7 2 3 1

    }
    //使用层序遍历、加上一个栈
    // 不同的是，入队列的顺序是先右后左，入栈之后近似正常的顺序了
    void levelOrderTraversalInReverse(BinaryTreeNode root){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        Stack<BinaryTreeNode> stack=new Stack<>();
        if (root==null) return;
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            if (temp.getRight()!=null) queue.offer(temp.getRight());
            if (temp.getLeft()!=null) queue.offer(temp.getLeft());
            stack.push(temp);
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop().getData());
        }
    }
}
